package com.ljx.offer;

import java.util.HashMap;

/**
 * @author 李捷禧
 * Date: 2023/3/25
 * ClassName: C_07
 */

public class C_07 {
        int[] preorder;
        HashMap<Integer, Integer> dic = new HashMap<>();

    /***
     * 还不是很理解。。。。
     * @param preorder
     * @param inorder
     * @return
     */
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++)
                dic.put(inorder[i], i);
            return recur(0, 0, inorder.length - 1);
        }
        TreeNode recur(int root, int left, int right) {
            if(left > right) return null;
            // 递归终止
            TreeNode node = new TreeNode(preorder[root]);
            // 建立根节点
            int i = dic.get(preorder[root]);
            // 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1);
            // 开启左子树递归
            node.right = recur(root + i - left + 1, i + 1, right);
            // 开启右子树递归
            return node;
            // 回溯返回根节点
        }

  public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }
}
